/**
 * 剑指 Offer 63. 股票的最大利润
 * https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
 */
public class Solutions_Offer_63 {
    public static void main(String[] args) {
//        int[] prices = {7, 1, 5, 3, 6, 4};  // output: 6 - 1 = 5
        int[] prices = {7, 6, 4, 3, 1};  // output: 0

        int result = maxProfit(prices);
        System.out.println(result);
    }

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE, res = 0;
        for (int price : prices) {
            if (price < min) {
                // 更新最小买入费用
                min = price;
            } else {
                // 仅当 price 大于等于 min 时，即卖出不会亏损
                // 此时可以卖出，获得利润，那么比较最大利润
                res = Math.max(res, price - min);
            }
        }
        // 怎么买卖都不会亏，因为可以选择不买
        return res;
    }
}
